from python算法.Graph.Ljt import graph
from collections import defaultdict
class solution():
    def __init__(self,file=None):
        # super().__init__(file)
        self.__preorder = []
        self.__postorder = []
        self.cg = graph(file)
        self.G = self.cg.readGraph()
        self.V  = self.cg.getV
        self.E = self.cg.getE
        self.__visited = [-1]*self.V#用来记录多个联通分量的首个Node或者可以说记录图中的节点是否被访问
        self.__Cpnumber = 0#图的连通数量的个数
        self.__raodprenode = [-1]*self.V#用来保存被访问节点的前一个节点


    def GetCpNumber(self):
        return self.__Cpnumber

    def LtFlInfo(self):
        self.ltflinfo = defaultdict(list)
        self.GetPreDfsOrder()
        for node,val in enumerate(self.__visited):
             self.ltflinfo[val].append(node)
        return self.ltflinfo

    def GetPreDfsOrder(self):
        for i in range(self.V):
            if self.__visited[i]==-1:
                self.__dfs(i,self.__Cpnumber)#一个节点得到一个联通分量
                self.__Cpnumber+=1
        return self.__preorder

    def GetPostDfsOrder(self):
        for i in range(self.V):
            if not self.__visited[i]:
                self.__dfs(i)#一个节点得到一个联通分量
        return self.__postorder

    def GetPath(self,origin,target):
        # if not self.isConnect(origin,target):
        #     return []
        self.__singleRoadDfs(origin,-2)
        if self.__raodprenode[target] == -1:
            return None
        res = [ ]
        cur = target
        res.append(str(cur))
        #从后往前推路径
        while cur!=origin:
            res.append(str(self.__raodprenode[cur]))
            cur = self.__raodprenode[cur]
        print("{}---->{}的一条连通路径:{}".format(origin,target,"-->".join(res[::-1])))


    def __singleRoadDfs(self,o,parent):
        #找出点到点之间的一条路径
        self.__raodprenode[o]=parent
        for i in self.cg.adjacentVertices(o):
            if  self.__raodprenode[i]==-1:
                self.__singleRoadDfs(i,o)

    def __dfs(self,v,nodeid):
        self.__preorder.append(v)
        self.__visited[v] = nodeid
        for i in self.cg.adjacentVertices(v):
            if  self.__visited[i]==-1:
                self.__dfs(i,nodeid)
        self.__postorder.append(v)
if __name__ == '__main__':
    s = solution(r"D:\tensorflow2_pytorch\python算法\Graph\ltflbl.txt")
    print("图的先序优先遍历：",s.GetPreDfsOrder())
    # print("图的后序优先遍历：",s.GetPostDfsOrder())
    print(s.G)
    print(s.GetCpNumber())
    print(s.LtFlInfo())
    s.GetPath(4,6)